package com.power.algorithm.sort;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/5/25 11:20 上午
 */
public class QuickSort {

    public static void main(String[] args) {
        //  int[] arr = Tools.createOrigin10Array();


        int[] arr = new int[]{29, 12, 35, 56, 25};
        QuickSort quickSort = new QuickSort();
        quickSort.display(arr);
        quickSort.sort(arr, 0, arr.length - 1);
        quickSort.display(arr);
    }


    public void display(int[] arr) {
        System.out.print("元素:: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public void sort(int[] array, int front, int rear) {
        /**
         * 1. 找到一个基准数字
         * 2. 移动到合适的位置
         * tmp = array[0]
         * 如果j = array[length-1]
         */
        int i = front;
        int j = rear;
        int key = array[front];

        while (i < j) {
            //从右向左进行位移  直到找到比tmp小的值
            while (i < j && array[j] >= key) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            //从左向右移动  直到找到比tmp大的值
            while (i < j && array[i] <= key) {
                i++;
            }
            //如果不满足条件就交换位置
            if (i < j) {
                array[j] = array[i];
                j--;
            }

            display(array);
        }
        array[i] = key;
        System.out.print("第一次结束:: ");
        display(array);
        if (front < i - 1) {
            this.sort(array, front, i - 1);
            System.out.print("第二次结束:: ");
            display(array);
        }

        if (i + 1 < rear) {
            this.sort(array, i + 1, rear);
            System.out.print("第三次结束:: ");
            display(array);
        }

    }
}
